package com.lmk.dsa.algorithm.sort;

import java.security.SecureRandom;
import com.lmk.dsa.struct.commons.KvNode;
import com.lmk.dsa.struct.heap.*;

/**
 * 数组排序工具类
 * @author LaoMake
 * @since 1.0
 */
public class ArraySort {
	
	private static SecureRandom random = new SecureRandom();
	
	/**
	 * 快速排序
	 * @param array
	 */
	public static void quickSort(KvNode[] array) {
		_quickSort(array, 0, array.length - 1);
	}
	
	
	private static void _quickSort(KvNode[] array, int L, int R) {
		if(R <= L){
			return;
		}

		int index = random.nextInt(R - L) + L;
		if(index != L) {
			swap(array, L, index);
		}
		
		
		if(L != R){
			int j = L;
			int i = L + 1;
			
			while(i <= R) {
				if(array[i].compareTo(array[L]) < 0) {
					swap(array, ++j, i);
				} 
				i++;
			}
			
			if(j != L) {
				swap(array, L, j);
				_quickSort(array, L, j - 1);
			}
			
			if(j != R)
				_quickSort(array, j + 1, R);
		}
	}
	
	
	/**
	 * 原地堆排序
	 * @param array
	 * @return
	 */
	public static void heapSort(KvNode[] array) {
		new MaxHeap(array).sort();
	}

	/**
	 * 基数排序
	 * @param array
	 * @return
	 */
	public static void baseSort(KvNode<Integer, Object>[] array) {
		KvNode[][] buckets = new KvNode[10][array.length];
		int min = 0;
		int div = 10;
		do{
			int[] bucketSize = new int[10];
			min = 0;
			for(int i = 0; i < array.length; i++) {
				// 记录最大商，以便判断时候还需要进行更高位的计算
				int temp = array[i].key / div;
				if(temp > min) {
					min = temp;
				}

				int bucket = array[i].key / (div / 10) % 10;
				int bucketIndex= bucketSize[bucket];

				buckets[bucket][bucketIndex] =  array[i];
				bucketSize[bucket] = bucketIndex + 1;
			}

			div *= 10;

			int index  = 0;
			for(int i = 0; i < 10; i++) {
				for(int j = 0; j < bucketSize[i]; j++) {
					array[index++] = buckets[i][j];
				}
			}
		}while(min > 0);
	}
	
	/**
	 * 归并排序
	 * @param array
	 * @return
	 */
	public static KvNode[] mergeSort(KvNode[] array) {
		return mergeSort(array, 0, array.length - 1);
	}
	
	private static KvNode[] mergeSort(KvNode[] array, int L, int R) {
		KvNode[] result;
		int size = (R - L + 1) / 2;
		if(size > 0) {
			KvNode[] left = mergeSort(array, L, L + size - 1);
			KvNode[] right = mergeSort(array, L + size, R);
			
			result = merge(left, right);
		}else {
			result = new KvNode[] {array[L]};
		}
		return result;
	}
	
	/**
	 * 合并算法
	 * @param a
	 * @param b
	 * @return
	 */
	private static KvNode[] merge(KvNode[] a, KvNode[] b) {
		KvNode[] c = new KvNode[a.length + b.length];
		
		int left = 0;
		int right = 0;
		
		for(int i = 0; i < c.length; i++) {
			if(left == a.length) {
				c[i] = b[right++];
				continue;
			}
			
			if(right == b.length) {
				c[i] = a[left++];
				continue;
			}
			
			if(a[left].compareTo(b[right]) < 0) {
				c[i] = a[left++];
			}else {
				c[i] = b[right++];
			}
		}
		return c;
	}

	
	/**
	 * 插值排序
	 * @param array
	 */
	public static void insert(KvNode[] array) {
		for(int i = 1; i < array.length; i++) {
			if(array[i].compareTo(array[i - 1]) < 0) {
				int j = i;
				KvNode v = array[j];
				
				while(j > 0 &&  array[j - 1].compareTo(v) > 0) {
					array[j] = array[j - 1];
					j--;
				}
				array[j] = v;
			}
		}
	}
	
	
	/**
	 * 选择排序
	 * @param array
	 */
	public static void select(KvNode[] array) {
		for(int i = array.length -1; i > 0; i--) {
			int index = 0;
			for(int j = 1; j <= i; j++) {
				if(array[j].compareTo(array[index]) > 0) {
					index = j;
				}
			}
			
			if(index != i) {
				swap(array, index, i);
			}
		}
	}
	
	/**
	 * 冒泡排序
	 * @param array
	 */
	public static void bubble(KvNode[] array) {
		for(int i = 0; i < array.length - 1 ; i++) {
			for(int j = 0; j < array.length - i - 1; j++) {
				if(array[j].compareTo(array[j + 1]) > 0) {
					swap(array, j, j + 1);
				}
			}
		}
	}
	
	/**
	 * 操作数组，将指定的两个索引位置的元素进行互换
	 * @param array
	 * @param index1
	 * @param index2
	 */
	public static void swap(KvNode[] array, int index1, int index2) {
		KvNode tmp = array[index1];
		array[index1] = array[index2];
		array[index2] = tmp;
	}
	
	
}
